\subsection{Burn}
\label{sec:20Burn}

We continue with the notation and indices from the prior sections.\\
\\
Suppose Bob is the owner of the token commitment $Z_e$ which represents a value of $e$ (denominated in the currency of a particular ERC-20 token).\\
\\
Recall that whilst the token commitment $Z_e$ exists (read: ``is spendable'') within the Shield contract, the Shield contract holds an equivalent value of $e$ `public' ERC-20 tokens; effectively `locked up' in escrow.\\
\\
Suppose Bob (now the owner of $Z_e$ because he knows the secret key $sk_B$) wishes to `release' a value of $e$ ERC-20 tokens from escrow.
Then he will need to effectively `reveal' the contents of his token commitment $Z_e$ in order to convince the Shield contract that he is indeed entitled to withdraw $e$ from escrow.
We call this act of converting from a `private' token commitment back to its `public' counterpart a `\textbf{burn}'.
\\
Note that by burning a token commitment, Bob is revealing information which was previously private; namely, the value $e$. Bob could continue to use an anonymous Ethereum address when calling the `burn' transaction, but analytics of public ERC-20 transactions thereafer will likely eventually reveal that it was Bob who burned $e$. We'll have Bob use his public Ethereum address `burn', for simplicity.\\
\\

\noindent
For Bob to burn $Z_e$ within the Shield contract, under zero knowledge, he follows the steps in Figure~\ref{fig:fBurnAlgorithm}.

\begin{figure}[htp]
  \ContinuedFloat*
	\begin{center}
		\begin{framed}
      \begin{tabular}{p{16cm}}	
        \textbf{Fungible burn algorithm} \\
        \\
        \midrule
        \textbf{Bob's steps:}\\
        \begin{enumerate}
          \setcounter{enumi}{\value{ongoingEnumCounter}}
          \item Compute $N_e := h(\;\sigma_e\;|\;sk^Z_B\;)$, the nullifier of Bob's commitment $Z_e$.
          \item Get $\psi_{Z_e}$ -- the sister-path of $Z_e$ -- from the Shield contract (see Details below).
          \item Get the latest Merkle root from the Shield contract: $\roott_{n+m+k+l}$ (see Details below).
          \item Set public inputs $x = (\;e,\;N_e,\;\roott_{n+m+k+l})$
          \item Set private inputs $\omega = (\psi_{Z_e},\;sk_B,\;\sigma_e)$
          \item Select $C_{ft-burn}(\;\omega,\;x\;)$ -- the set of constraints which are satisfied if and only if:
          \begin{enumerate}
            \item $pk_B$ equals $h(\;sk_B\;)$; (Proof of knowledge of the secret key to $pk_B$) (see Details for why $pk_B$ isn't an input to $C$)
            \item $Z_e$ equals $h(\;e\;|\;pk_B\;|\;\sigma_e\;)$ (Proof of the constituent values of $Z_c$)
            (See Details for why $Z_e$ isn't an input to $C$)
            \item $\roott_{n+m+k+l}$ equals $h\br*{\psi_{Z_e}(1)\;|...|\;h\br*{\psi_{Z_e}(d-2)\;|\;h\br*{\psi_{Z_e}(d-1)\;|\;Z_e}\;}...}$ (Proof that $Z_e$ belongs to the on-chain Merkle Tree)
            \item $N_e$ equals $h(\;\sigma_e\;|\;sk^Z_B\;)$ (Proof that $N_e$ is indeed the nullifier of $Z_e$)
          \end{enumerate}
          \item Generate $\pi := P(\;p_C\;,\;x,\;\omega\;)$; a proof of knowledge of satisfying arguments $(\omega, x)\;s.t.\;C(\omega, x) = 1$. Recall: $p_C$ -- the proving key for $C$ -- will be stored on Alice's computer.
           
          The pair $(\pi, x)$ is the zk-SNARK which attests to knowledge of private inputs $\omega$ without revealing them.
          \item Send $(\pi, x)$ to the Shield contract for verification.
           
          Using web3: \texttt{fTokenShield.burn(payTo, proof, inputs, vkId)}

          where \texttt{payTo} is an Ethereum address, specified by Bob, into which he wishes for $e$ to be transferred (denominated in the currency of the linked ERC-20 contract).
          %remember where the count (enumi) is up to and store it in ongoingEnumCounter:
          \setcounter{ongoingEnumCounter}{\value{enumi}}
        \end{enumerate}
        \ \\
        \midrule
        \textbf{Shield contract's steps:}\\
        \begin{enumerate}
          %resume counter
          \setcounter{enumi}{\value{ongoingEnumCounter}}
          \item Verify the proof as correct: call a Verifier contract to verify the \texttt{(proof, inputs)} pair against the verification key represented by \texttt{vkId}.
          \setcounter{ongoingEnumCounter}{\value{enumi}}
        \end{enumerate}
        \ \\
        \midrule
        ... 
			\end{tabular}
		\end{framed}
	\end{center}
\caption{Fungible Burn Algorithm}
\label{fig:fBurnAlgorithm}
\end{figure}

%continue on next page
\begin{figure}[htp]
  \ContinuedFloat %to continue
	\begin{center}
		\begin{framed}
      \begin{tabular}{p{16cm}}
       \textbf{ Verifier contract's steps:}\\
        \begin{enumerate}
          \setcounter{enumi}{\value{ongoingEnumCounter}}
          \item Compute \texttt{result = verify(proof, inputs, vkId)}.
          
          I.e. Verify the \texttt{(proof, inputs)} pair against the verification key.
          \item Return \texttt{result}$\in$\texttt{\{false, true\}} to the Shield contract.
          \setcounter{ongoingEnumCounter}{\value{enumi}}
        \end{enumerate}
        \ \\
        \midrule
        \textbf{Shield contract's steps:}\\
        \begin{enumerate}
          \setcounter{enumi}{\value{ongoingEnumCounter}}
          \item If \texttt{result = false}, revert.
          \item Else:
          \begin{enumerate}
            \item Check $\roott_{n+m+k+l}$ is in $\rootsList$. (Revert if not).
            \item Check $N_e$ is not already in its list of `spent' nullifiers. (Revert if not).
            \item Transfer ERC-20 tokens of value $e$ from the Shield contract (which has been holding the value in escrow) to Bob's \texttt{payTo} Ethereum address.
            \item Append the nullifier $N_{e}$ to the ever-increasing array $\bm N$.
          \end{enumerate}
          \setcounter{ongoingEnumCounter}{\value{enumi}}
        \end{enumerate}
        \ \\
        \midrule
        \textbf{Bob's steps:}\\
        \begin{enumerate}
          \setcounter{enumi}{\value{ongoingEnumCounter}}
          \item Check the ERC-20 contract to ensure his balance has increased by $e$.
          \item Store any relevant data in his local database.
          \setcounter{ongoingEnumCounter}{0} %reset for next figure
        \end{enumerate} 
			\end{tabular}
		\end{framed}
	\end{center}
\caption{Fungible Burn Algorithm} %same caption as the first part of this figure
%\label{fig:nfTransferAlgorithm} - no label in this second part of the figure
\end{figure}






\newpage
\subsubsection{Details}
\label{sec:20BurnDetails}

We refer to the numbered steps of Figure~\ref{fig:fBurnAlgorithm}.\\
\\

\textbf{Step $1$}
\ \\
This is handled within \hyperref[sec:f-token-controller]{\texttt{f-token-controller.js}}.\\
\\

\textbf{Steps $2 - 3$}
\ \\
These calls to the Shield contract are handled within \hyperref[sec:f-token-zkp]{\texttt{f-token-zkp.js}}.\\
\\
\noindent
It is important at this stage to note that there are an unknown number of other parties utilising the Shield smart contract.
Hence, the dynamic array of tokens $\bm{Z}$ might have grown since Alice appended Bob's $Z_e$ and Alice's $Z_f$ as the $(n+m)^{th}$ and $(n+m+1)^{th}$ leaves of $M$.
Suppose there have been $l-1$ additional tokens added to $\bm{Z}$ since then.
That is,\\
\begin{align*}
  \bm{Z}_{n+m+k-1} = (Z_0, Z_1,...,Z_{n-1}, Z_c, ..., Z_{n+m-1}, Z_d,..., Z_{n+m+k-1}, Z_e, Z_f, Z_{n+m+k+2}, ... Z_{n+m+k+l})
\end{align*}

\noindent
We denote the corresponding Merkle Tree which holds tokens $\bm{Z}_{n+m+k+l}$ by $M_{n+m+k+l}$. We denote its root by $\roott_{n+m+k+l}$; an element of $\rootsList$.


\begin{align*}
  \scalebox{0.85}{
    \begin{forest}
      [{$\roott_{n+m+k+l}:= h\br*{
                          h\br*{
                            h\br*{
                              h\br*{
                                Z_0,Z_1
                              },
                              ...
                            },
                            h\br*{
                              h\br*{
                                Z_{n-1},Z_c
                              },
                              h\br*{
                                ...,Z_{n+m-1}
                              }
                            }
                          },
                          h\br*{
                            h\br*{
                              h\br*{
                                Z_d, ...
                              },
                              h\br*{
                                Z_{n+m+k-1}, Z_e
                              }
                            },
                            h\br*{
                              h\br*{
                                Z_f, ...
                              },
                              h\br*{
                                Z_{n+m+k+l}, 0
                              }
                            }
                          }
                        }
                      $}
        [{$ h\br*{
              h\br*{
                h\br*{
                  Z_0,Z_1
                },
                ...
              },
              h\br*{
                h\br*{
                  Z_{n-1},Z_c
                },
                h\br*{
                  ...,Z_{n+m-1}
                }
              }
            }
          $}
          [{$ h\br*{
                h\br*{
                  Z_0,Z_1
                },
                ...
              }
            $}
            [{$ h\br*{
                  Z_0,Z_1
                }
              $}
              [{$Z_0$}][{$Z_1$}]
            ]
            [...
              [...][...]
            ]
          ]
          [{$ h\br*{
                h\br*{
                  Z_{n-1},Z_c
                },
                h\br*{
                  ...,Z_{n+m-1}
                }
              }
            $}
            [{$ h\br*{
                  Z_{n-1},Z_c
                }
              $}
              [{$Z_{n-1}$}][{$Z_c$}]
            ]
            [{$ h\br*{
                  ...,Z_{n+m-1}
                }
              $}
              [...][{$Z_{n+m-1}$}]
            ]
          ]
        ]
        [{$ h\br*{
              h\br*{
                h\br*{
                  Z_d, ...
                },
                h\br*{
                  Z_{n+m+k-1}, Z_e
                }
              },
              h\br*{
                h\br*{
                  Z_f, ...
                },
                h\br*{
                  Z_{n+m+k+l}, 0
                }
              }
            }
          $}
          [{$ h\br*{
                h\br*{
                  Z_d, ...
                },
                h\br*{
                  Z_{n+m+k-1}, Z_e
                }
              }
            $}
            [{$ h\br*{
                  Z_d, ...
                }
              $}
              [{$Z_d$}][...]
            ]
            [{$ h\br*{
                  Z_{n+m+k-1}, Z_e
                }
              $}
              [{$Z_{n+m+k-1}$}][{$Z_e$}]
            ]
          ]
          [{$ h\br*{
                h\br*{
                  Z_f, ...
                },
                h\br*{
                  Z_{n+m+k+l}, 0
                }
              }
            $}
            [{$ h\br*{
                  Z_f, ...
                }
              $}
              [{$Z_f$}][...]
            ]
            [{$ h\br*{
                  Z_{n+m+k+l}, 0
                }
              $}
              [{$Z_{n+m+k+l}$}][0]
            ]
          ]
        ]
      ]
    \end{forest}
  }
\end{align*}



\noindent
Bob retrieves the value of the current Merkle root, $\roott_{n+m+k+l}$, from the Shield contract.\\
\\
Since Bob knows that $Z_e$ is at leaf-index $n+m+k$ of $M_{n+m+k+l}$, Bob can also retrieve the path from the leaf $Z_{n+m+k}=Z_e$ to the root $\roott_{n+m+k+l}$. Path computations are done in \texttt{zkp/src/format-inputs.js}.\\
\\
We denote this path
\begin{align*}
  \phi_{Z_e} = [\phi_{d-1}, \phi_{d-2},..., \phi_{1}, \phi_0]
\end{align*}
Note that $\phi_0 = \roott_{n+m+k+l}$.\\
\\
Bob also retrieve's the `sister-path' of this path:
\begin{align*}
  \psi_{Z_e} = [\psi_{d-1}, \psi_{d-2},..., \psi_{1}, \psi_0]
\end{align*}
where $\psi_0 = \phi_0 = \roott_{n+m+k+l}$.\\
\\
For ease of reading, let's focus only on the nodes of $M_{n+m+k+1}$ which Bob cares about for the purposes of burning his token commitment $Z_e$:


\begin{align*}
  \scalebox{0.85}{
    \begin{forest}
      [{$\roott_{n+m+k+l}:= \phi_{0} = \psi_{0}$}
        [{$\psi_{1}$}
          [...
            [...
              [...][...]
            ]
            [...
              [...][...]
            ]
          ]
          [...
            [...
              [...][...]
            ]
            [...
              [...][...]
            ]
          ]
        ]
        [{$\phi_{1}$}
          [{$\phi_{2}$}
            [{$\psi_{3}$}
              [...][...]
            ]
            [{$\phi_{3}$}
              [{$\psi_{4}$}][{$Z_e$}]
            ]
          ]
          [{$\psi_{2}$}
            [...
              [...][...]
            ]
            [...
              [...][0]
            ]
          ]
        ]
      ]
    \end{forest}
  }
\end{align*}


\noindent
Equipped with $\psi_{Z_e}$, Bob can prove that he owns a token commitment at one of the leaves of $M_{n+m+k+l}$, without revealing that it is "$Z_{n+m+k}$ located at leaf-index $n+m+k$".\\
\\

\textbf{Steps $4-5$}
\ \\
These steps are handled within \hyperref[sec:f-token-controller]{\texttt{f-token-controller.js}}.\\
\\
As a reminder, we let:
\begin{center}
  \begin{tabular}{l l}
    $x = (e,\
          N_{e},\
          \roott_{n+m+k+l})$ & Public Inputs used to generate the Proof\\
    $\omega = (\psi_{Z_e},\
              sk_B,\
              \sigma_e)$ & Private Inputs used to generate the Proof\\
  \end{tabular}
\end{center}
\ \\




\textbf{Steps $6 - 7$}
\ \\
These steps are handled within a \hyperref[sec:zokrates]{ZoKrates} container.\\
\\
Bob uses the $C_{ft-burn}$ (or $C$) -- the set of constraints for a fungible burn, located in \texttt{zkp/code/gm17/ft-burn} (see \hyperref[sec:trustedSetup]{Trusted Setup}). $C_{ft-burn}(\;\omega,\;x\;)$ returns a value of $true$ if Bob provides a set of valid `satisfying' arguments $(\omega, x)$ to $C$.\\
\\
Let's elaborate on each of the checks and calculations constraining the inputs to $C$ (we highlight public inputs in \textbf{bold} below):
\begin{enumerate}
  \item Calculate $h(sk_B) =: pk_B'$.\\
    Note that this newly calculated $pk_B'$ should equal $pk_B$ (Bob's public key), but we don't need to pass $pk_B$ as a private input and explicitly check that $pk_B'=pk_B$; a check on the correctness of $sk_B$ (and hence $pk_B'$) is implicitly achieved in the next two steps:
  \item Calculate $h(\bm{e}\;|\;pk_B'\;|\;\sigma_e) =: Z_e'$.\\
    Note again that this newly calculated $Z_e'$ should equal $Z_e$ (Bob's token commitment), but we don't need to pass $Z_e$ as a private input and explicitly check that $Z_e'=Z_e$; a check on the correctness of $Z_e$ (and hence $Z_e'$) is implicitly achieved in the next step:
  \item Check inputs $\psi_{Z_e}=[\psi_{d-1}, \psi_{d-2},..., \psi_{1}, \bm{\psi_{0}=\roott_{n+m+k+l}}]$ and the newly calculated $Z_e'$ satisfy:\\
    $h\br*{\psi_{1}\;|...|\;h\br*{\psi_{d-2}\;|\;h\br*{\psi_{d-1}\;|\;Z_B'}\;}...} = \roott_{n+m+k+l} ( =: \bm{\psi_{0}})$\\
    Given the one-way nature of our hashing function $h$, the only feasible way we could have arrived at the correct value of $\roott_{n+m+k+l}$ is if the sister-path $\psi_{Z_e}$ is correct, and if $Z_e'$ is correct, which (working backwards) must mean that $sk_B$ is correct.

    How does the circuit know the value of $\roott_{n+m+k+l}$ is correct? It doesn't; but it is a `public input', and we can rely upon the Shield smart contract to check the correctness of all public inputs.\\
  \\
  We've therefore shown in the steps so far, that:
  \begin{itemize}
    \item[--] Bob is the owner of a token commitment (because he knows its secret key)
    \item[--] Said token commitment is indeed a leaf of the on-chain Merkle Tree $M_{n+m+k+l}$.
    \item[--] The token commitment does indeed represent a value of $e$ ERC-20 tokens (remember that $e$ is a public input to a `burn' zk-SNARK).
  \end{itemize}

  Bob commits to burning his token $Z_e$ in the next step:
  \item Check inputs $\sigma_e, sk_B, \bm{N_e}$ satisfy:
    $h(\sigma_e\;|\;sk_B) = \bm{N_e}$\\
    $N_e$ is referred to as a `nullifier' because it is understood by all participants to be an indisputable commitment to spend (`nullify') a token commitment. Remember that the token commitment being spent isn't revealed; the earlier steps have allowed Bob to demonstrate hidden knowledge of the secret key $sk_B$ of a token commitment which does indeed exist. By including $sk_B$ in the nullifier's preimage, Bob is binding himself as the executor of this `burn'. By including $\sigma_e$, Bob is specifying a serial number which is unique to the token $Z_e$ (thereby distinguishing this nullifier from those which would nullify any other token commitments he may own).
\end{enumerate}
Notice how each stage is linked to the last, and that at each of the `Check' stages, private inputs are being reconciled against at least one public input (highlighted in \textbf{bold} to help you notice). By structuring the circuit $C$ in this way, we are able to share only the public inputs with the Shield contract (along with a `proof' $\pi_{C,x,\omega}$). We'll see shortly that the Shield contract checks the correctness of each of the public inputs against its current states.\\
\\

\noindent
If all of the above constraints are satisfied by the public and private inputs, ZoKrates will generate the proof $\pi_{C,x,\omega}$; a proof of knowledge of satisfying arguments $(\omega, x) \ s.t. \ C(\omega, x) = 1$.\\
\\







\textbf{Step $8$}
\ \\
This transaction is handled within \hyperref[sec:f-token-zkp]{\texttt{f-token-zkp.js}}.\\
\\
Having generated $\pi_{C,x,\omega}$, Bob then sends the following to the Shield contract from his Ethereum address $E_B$:
\begin{align*}
  &E_B\\
  &\pi_{C,x,\omega}\\
  &x = (e, N_{e}, \roott_{n+m+k+l})
\end{align*}
\\
Recall that everyone knows the checks and calculations which have been performed in the circuit $C_{ft-burn}$, because it is a public file in the Nightfall repository. Further, everyone knows the verification key $vk_C$ which uniquely represents this circuit, because it has been publicly stored in the Verifier Registry contract. Therefore, when Bob shares the pair $(x, \pi_{C,x,\omega})$, and the `unique id' of the relevant verification key $vk_C$; everyone will interpret this information as the Bob's intention to burn; and everyone will be convinced that he knows the secret key which permits him to transfer ownership of a token commitment; and everyone will be convinced that that token commitment represents a value of $e$ ERC-20 tokens.\\
\\


\textbf{Steps $9 - 11$}
\ \\
The Verifier Registry contract already has stored within it the verification key $vk_C$.
It runs a verification function $V(vk_C, \pi_{C,x,\omega}, x)$.
\begin{align*}
  V: (vk_C, \pi_{C,x,\omega}, x) \to \{0,1\}
\end{align*}
where:
\[
    V=
\begin{cases}
    1,& \text{if } \pi_{C,x,\omega} \text{ and } x \text{ satisfy } vk_C\\
    0,& \text{otherwise}
\end{cases}
\]
\ \\




\textbf{Steps $12 - 13$}
\ \\
If the Verifier contract returns $1$ ($true$) (verified) to the Shield contract, then the Shield contract will be satisfied that Bob's proof and public inputs represent his commitment to burning a token commitment, and to withdrawing its underlying ERC-721 token $=\alpha$. If the Verifier contract returns $0$, then the transaction will revert.\\
\\
Let's suppose Bob's $(x, \pi_{C,x,\omega})$ pair is verified.\\
\\
Following verification of the proof, the Shield contract will do the following:
\begin{enumerate}
  \item Check $\roott_{n+m+k+l}$ is in $\rootsList$.\\
    (If not, the burn will fail)
  \item Check $N_e$ is not already in the list of nullifiers, which we denote $\bm{N}$.\\
    (If $N_e$ is already in $\bm{N}$, the burn will fail)
  \item Transfer a value of $e$ ERC-20 tokens from the Shield contract (i.e. from escrow) to Bob's Ethereum address.
  \item Append the nullifier $N_e$ to the ever-increasing array $\bm N$.
\end{enumerate}
\ \\

\textbf{Steps $14 - 15$}
\ \\
Bob is now the owner of $e$ more ERC-20 tokens. The Nightfall UI queries the linked ERC-20 contract for tokens Bob owns.
If Bob ever wished to convert some or all of this value back into a token commitment, he would need to do a fungible `mint' (discussed earlier).